{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 知识准备\n",
    "\n",
    "* 决策树算法原理\n",
    "* python语言\n",
    "* math模块中的log函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "import operator\n",
    "from math import log"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 决策树算法原理回顾\n",
    "\n",
    "**对样本分类的树形结构。**\n",
    "\n",
    "1. 节点\n",
    "    * 叶节点(样本类别)、内部节点(特征)\n",
    "    * 纯节点、不纯节点\n",
    "    * 节点不纯度\n",
    "        * 熵不纯度   \n",
    "        $Ent(D) = -\\displaystyle\\sum_{i=1}^{k}p_ilog_2p_i$\n",
    "        \n",
    "        * Gini不纯度   \n",
    "        $Gini(D) = 1 - \\displaystyle\\sum_{i=1}^{k}p_i^2$\n",
    "        \n",
    "        * 误差不纯度\n",
    "\n",
    "\n",
    "2. 选择特征\n",
    "    * 基于熵的信息增益(ID3) \n",
    "    \n",
    "    $Gain(D, a)=Ent(D)-\\displaystyle\\sum_{v=1}^{V}{\\frac{|D^{v}|}{|D|}}Ent(D^{v})$\n",
    "    \n",
    "    * 基于熵的信息增益比(C4.5) \n",
    "    \n",
    "    $Gain\\_r(D,A)=\\large \\frac{Gain(D,a)}{IV(a)}$ \n",
    "    \n",
    "    $IV(a)=-\\displaystyle\\sum_{v=1}^{V}{\\frac{|D^v|}{|D|}}log_2{\\frac{|D^v|}{|D|}}$\n",
    "    \n",
    "    * 基于Gini系数(CART)\n",
    "    \n",
    "    $Gini(D,a)=\\displaystyle {\\frac{|D^1|}{|D|}}Gini(D^1)+{\\frac{|D^2|}{|D|}}Gini(D^2)$\n",
    "  \n",
    "  \n",
    "3. 决策树(ID3)的实现\n",
    "    * **创建树形结构**\n",
    "        * 判断终止条件。(纯节点；用完特征)\n",
    "        * 选择最优特征。(将其加入树字典，删除已用特征)\n",
    "        * 遍历每个特征值，拿到对应子集来递归创建树。\n",
    "    * 准备工作\n",
    "        * 准备数据集\n",
    "        * 计算熵\n",
    "        * 划分子集\n",
    "        * 选择最优特征"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. 准备数据集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_dataset():\n",
    "    dataset = [[0, 0, 0, 0, 'no'],\n",
    "             [0, 0, 0, 1, 'no'],\n",
    "             [0, 1, 0, 1, 'yes'],\n",
    "             [0, 1, 1, 0, 'yes'],\n",
    "             [0, 0, 0, 0, 'no'],\n",
    "             [1, 0, 0, 0, 'no'],\n",
    "             [1, 0, 0, 1, 'no'],\n",
    "             [1, 1, 1, 1, 'yes'],\n",
    "             [1, 0, 1, 2, 'yes'],\n",
    "             [1, 0, 1, 2, 'yes'],\n",
    "             [2, 0, 1, 2, 'yes'],\n",
    "             [2, 0, 1, 1, 'yes'],\n",
    "             [2, 1, 0, 1, 'yes'],\n",
    "             [2, 1, 0, 2, 'yes'],\n",
    "             [2, 0, 0, 0, 'no']]\n",
    "    feat_labels = ['年龄', '有工作', '有房子', '信贷情况']\n",
    "    return dataset, feat_labels;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['年龄', '有工作', '有房子', '信贷情况']"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dataset, feat_labels = create_dataset()\n",
    "feat_labels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. 计算熵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_ent(dataset):\n",
    "    n = len(dataset)\n",
    "    # 统计各类别的样本数\n",
    "    label_count = {}\n",
    "    for x in dataset:\n",
    "        label = x[-1]\n",
    "        label_count[label] = label_count.get(label, 0) + 1\n",
    "    ent = 0\n",
    "    for key in label_count:\n",
    "        p = label_count[key] / n \n",
    "        ent -= p * log(p, 2)\n",
    "    return ent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. 划分子集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_dataset(dataset, feat_i, value):\n",
    "    sub_dataset = []\n",
    "    for x in dataset:\n",
    "        if x[feat_i] == value:\n",
    "            x_a = x[:feat_i]\n",
    "            x_a.extend(x[feat_i + 1 :])\n",
    "            sub_dataset.append(x_a)\n",
    "    return sub_dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. 选最优特征"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def choose_best_feat(dataset):\n",
    "    best_feat = -1\n",
    "    best_gain = 0\n",
    "    ent_base = calc_ent(dataset)\n",
    "    feat_n = len(dataset[0]) - 1\n",
    "    for feat_i in range(feat_n):\n",
    "        value_list = [x[feat_i] for x in dataset]\n",
    "        unique_vals = set(value_list)\n",
    "        ent_new = 0\n",
    "        for value in unique_vals:\n",
    "            sub_dataset = split_dataset(dataset, feat_i, value)\n",
    "            n1 = len(sub_dataset)\n",
    "            n = len(dataset)\n",
    "            ent_new += n1 / n * calc_ent(sub_dataset)\n",
    "        gain_i = ent_base - ent_new\n",
    "        if gain_i > best_gain:\n",
    "            best_gain = gain_i\n",
    "            best_feat = feat_i\n",
    "    return best_feat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# choose_best_feat(dataset)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5.创建树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_tree(dataset, feat_labels):\n",
    "    # 判断终止条件\n",
    "    class_labels = [x[-1] for x in dataset]\n",
    "    if class_labels.count(class_labels[0]) == len(class_labels):\n",
    "        return class_labels[0]\n",
    "    if len(dataset[0]) == 1:\n",
    "        class_count = {}\n",
    "        for c in class_labels:\n",
    "            class_count[c] = class_count.get(c, 0) + 1\n",
    "        sorted_class = sorted(class_count.items(),\n",
    "                             key=operator.itemgetter(1),\n",
    "                             reverse = True)\n",
    "        return sorted_class[0][0]\n",
    "    \n",
    "    # 选择最优特征\n",
    "    best_feat_index = choose_best_feat(dataset)\n",
    "    best_feat_label = feat_labels[best_feat_index]\n",
    "    my_tree = {best_feat_label:{}}\n",
    "    feat_labels_a = feat_labels[:best_feat_index]\n",
    "    feat_labels_a.extend(feat_labels[best_feat_index + 1 :])\n",
    "    \n",
    "    # 遍历最优特征的每一个特征值，拿到子集，并递归创建树\n",
    "    value_list = [x[best_feat_index] for x in dataset]\n",
    "    unique_vals = set(value_list)\n",
    "    for value in unique_vals:\n",
    "        sub_dataset = split_dataset(\n",
    "            dataset,best_feat_index, value)\n",
    "        my_tree[best_feat_label][value] = create_tree(\n",
    "            sub_dataset,feat_labels_a)\n",
    "    return my_tree\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'有房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_tree = create_tree(dataset, feat_labels)\n",
    "my_tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6.分类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classify(my_tree, x, feat_labels):\n",
    "    root_feat = next(iter(my_tree))\n",
    "    branch = my_tree[root_feat]\n",
    "    feat_index = feat_labels.index(root_feat)\n",
    "    for key in branch.keys():\n",
    "        if x[feat_index] == key:\n",
    "            if type(branch[key]).__name__ == 'dict':\n",
    "                class_label = classify(branch[key], x, feat_labels)\n",
    "            else:\n",
    "                class_label = branch[key]\n",
    "    return class_label"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'yes'"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [0, 1, 0, 1]\n",
    "classify(my_tree, x, feat_labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
